1. The Basics

Basic Definitions and notation

Set is a collection of items, name elements, characterised by a certain property $A = \{ 2,4,7,D,24\}$ Element $x$ belgons to $A$ indicated as $x \in A$ Several elements of $A$ compose a subset $S:S\subset A$

Want to inidcate all the elements of the set: $\forall x \in A:$ Want to say there exists(at least) one element of $A$ which has a certain property (such that): $\exists x \in A \ni '$
Want to say there exists only/exactly one element of $A$ which has certain property $\exists! x \in A \ni '$ if statement 1 THEN statement 2 $\rightarrow$ statement 1 IF AND ONLY IF statement 2 $\iff$

Cardinality of a set

coincident - every element of $A$ is also an element of $B$ and every element of $B$ is also an element of $A$ cardinality of a set is number of elements contained in $A$ empty - indicated with $\emptyset$

Intersection and Union

intersection - $C = A \cap B$ - set containing all the elements that are both in the sets $A$ and $B$ union - $C = A \cup B$ - set containing all the elements that are either or both the sets $A$ and $B$ difference - $C = A \setminus B$ - set containing all the elements that are in $A$ but not $B$

Associativity of the Intersection

$(A\cap B) \cap C = A\cap (B\cap C)$

Numbers and Number sets

Set is finite if its cardinality is a finite number. Set is infinite if its cardinality is $\infty$ continuous if $\forall x_0 \in A:\exists x \ni ' |x-x_0|$

Types of Number Sets

Continue from last semester ℂ - Set of number than can be expressed as $a+jb$ where $a,b\in \R$ and the imaginary uni $j=\sqrt {-1}$

Cartesian Product

New set generated by all the possible pairs $C=A\times B$ $A=\{ 1,5,7\}$ $B=\{ 2,3\}$ $C=A\times B = \{ (1,2),(1,3),(5,2),(5,3),(7,2),(7,3)\}$

Relations

Order Relation

Indicated with $\preceq$ if following properties are verified:

• reflexivity
• transitivity
• antisymmetry

Example

Let $x,y \in \N$ and let consider $(x,y) \in \mathscr{R}$ if and only if $x$ is a multiple of $y$. More formally $(x,y)\in \mathscr{R}\iff \frac{x}{y} = k$ with $k\in \N$

Equivalence

Indicated with $\equiv$ if following properties are verified:

• Reflexivity - $x \equiv x$
• symmetry - $x\equiv y$ then $y\equiv x$
• transitivity - $x\equiv y$ and $y\equiv x$ then $x \equiv z$

Equivalence Classes

Let $\mathscr{R}$ be an equivalence relation defined on $A$. The equivalence class of an element $a$ is a set defined as $[a]=\{ x \in A|x \equiv a \}$

Partition

Set of all the elements equivalent to $a \in A$ is called equivalence class and is indicated with $[a]$

Functions/Mapping

Relation is to be a mapping or function when it relates to any element of a set unique element of another. Let $A$ and $B$ be two sets, a mapping $f:A \to B$ is a relation $\mathscr{R} \subseteq A\times B$ such that: $\forall x \in A\exists! y \in B\ni '(x,y) \in \mathscr{R}$ (Every element, find only 1 element in other set such that y is = x)

The statement $(x,y) \in \mathscr{R}$ can be expressed also as $y=f(x)$ Unary operator - $f:A \to B$ Binary operator - $f:A \times A \to B$ or $f:A\times C\to B$ Internal composition law - $f:A\times A\to A$

algebraic structure - set endowed with 1+ internal composition laws $(A,+,.)$

Injective Functions

$f A \to B$ is injection if the function values of two different elements is always different: $\forall x_1$ and $\forall x_2$ if $x_1 \ne x_2$ then $f(x_1) \ne f(x_2)$ Never crosses horizontal line twice. Doesnt cross it twice

Surjective Functions

$f A \to B$ is surjective if all elements of $B$ are mapped by an element of $A: \forall y\in B$ it follows that $\exists x \in A$ such that $y=f(x)$ Graph has no holes. Y axis as got a function, eg crosses graph

Bijective Functions

$f A \to B$ is bijective when both injection and surjection are verified